//1和0可以看做(和)，所谓的特殊的二进制序列就是合适的括号匹配对
//对于每个特殊的二进制序列，我们可以对其进行两种分解，如101100->10和1100，11011000->1+101100+0
//对于每个分解完的序列，我们可以递归调用使得其就是题目所需要的字典序最大的二进制
//由于可以任意交换相邻的二进制，因此将处理完的二进制直接排序，再组合起来就是当前的解
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution761 {
    public String makeLargestSpecial(String s) {
        if (s.length()==0){
            return "";
        }
        List<String> list=new ArrayList<>();
        int cur=0,last=0;
        for (int i=0;i<s.length();i++){
            if (s.charAt(i)=='1'){
                cur++;
            }else {
                cur--;
            }
            if (cur==0){
                list.add(s.substring(last,i+1));
                last=i+1;
            }
        }
        if (list.size()==1){
            return "1".concat(makeLargestSpecial(list.get(0).substring(1,list.get(0).length()-1))).concat("0");
        }else{
            for (int i=0;i<list.size();i++){
                list.set(i,makeLargestSpecial(list.get(i)));
            }
            list.sort(Comparator.reverseOrder());
            StringBuilder stringBuilder=new StringBuilder();
            for (String s1 : list) {
                stringBuilder.append(s1);
            }
            return stringBuilder.toString();
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution761().makeLargestSpecial("11011000"));
    }
}
